{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基本原理\n",
    "\n",
    "**决策树算法的基本流程**：\n",
    "1. 生成决策树（寻找纯净划分的过程）\n",
    "2. 剪枝\n",
    "3. 评估\n",
    "4. 预测"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 划分选择\n",
    "**什么是最优划分？什么是最优划分属性？**\n",
    "\n",
    "如果我们根据某个结点划分后，该结点的**纯度**相较于根据其他划分更高，我们就说这是当前结点的最优划分，选择的划分属性就是最优划分属性。\n",
    "\n",
    "上述提到的**纯度有多种定义方式：信息熵、增益率、基尼指数等**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 信息熵和信息增益\n",
    "假如当前样本集合$D$中第$k$个样本占比为$p_k(k=1,2,...,m)$,$m$是样本数，则**$D$的信息熵定义为**：\n",
    "$$Ent(D)=-\\sum_{k=1}^{m}p_klog_2p_k$$\n",
    "\n",
    "**对于信息熵的理解**：\n",
    "- 在上面的定义中，信息熵刻画了事件“集合$D$中的样本属于类别r”的不确定度（理解熵和信息，有个极好的[视频](https://www.zhihu.com/question/22178202)）\n",
    "\n",
    "**信息熵的重要结论**\n",
    "- 若$p=0$，约定信息熵等于0\n",
    "- 信息熵最小值为0（eg.样本集合全部属于某一个类别）;信息熵最大值为0（eg.样本集合在每个类别占比相同）\n",
    "- 信息熵越小，纯度越高；反之，纯度越低。\n",
    "\n",
    "若样本集D利用属性a划分为V个分支结点，则可以分别计算出每个子结点的信息熵然后为每个子节点赋予权重（即子节点的**归一化信息熵**），这样我们就定义了**用属性a对样本集D进行划分的信息增益（$D_v$表示第$v$个子结点的样本集）**：\n",
    "$$Gain(D,a)=Ent(D)-\\sum_{v=1}^{V}\\frac{|D_v|}{|D|}Ent(D_v)$$\n",
    "  \n",
    "  \n",
    "**信息增益的重要结论**\n",
    "- 信息增益越大，表示本次划分的纯度提升越大。因此，信息增益就可以作为划分的准则。\n",
    "  \n",
    "\n",
    "**信息增益作为划分标准的缺点**：\n",
    "- 信息增益准则下，倾向于使用属性值较多的属性作为划分依据，导致决策树泛化能力很差（极端场景：每个样本的在该属性下的属性值都不同，显然此时信息增益将最大，但显然没有意义）\n",
    "\n",
    "\n",
    "使用信息增益定义纯度的决策树算法有：\n",
    "- ID3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 增益率和固有属性值\n",
    "为了克服使用信息增益在选择属性时产生偏好带来的影响，引入了**增益率**来作为选择最优划分属性的依据。它定义为：\n",
    "$$Gain\\_ratio(D,a)=\\frac{Gain(D,a)}{IV(a)}$$，其中$IV(a)$叫做属性a的固有值:$$IV(a)=-\\sum_{v=1}^{V}\\frac{|D^v|}{|D|}log_2{|D^v|}{|D|}$$\n",
    "\n",
    "增益率与属性固有值的结论\n",
    "- 一般属性取值数目越多，固有值越大\n",
    "- 增益率偏向取属性值较少的属性作为最优划分属性\n",
    "\n",
    "\n",
    "使用增益率定义纯度的决策树算法：\n",
    "- C4.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基尼值和基尼指数\n",
    "\n",
    "数据集的纯度用基尼值定义：\n",
    "\n",
    "$$Gini(D)=\\sum_{k=1}^{|\\gamma |}\\sum_{k^{'}≠k}p_kp_{k^{'}}=1-\\sum_{k=1}^{|\\gamma|}p_k^2$$\n",
    "\n",
    "- 基尼值反映从数据集D中随机抽取两个样本，其类别不同的概率。\n",
    "\n",
    "**基尼值的重要结论**：\n",
    "\n",
    "- 数据集D基尼值越小，数据集D的纯度越高（抽取两个样本类别不同的概率较小，可见不确定性较小，基尼值也应该较小，数据越“纯”）\n",
    "\n",
    "\n",
    "\n",
    "数据集在属性a上划分点基尼指数定义：\n",
    "\n",
    "$$Gini_index(D,a)=\\sum_{v=1}^V \\frac{|D^v|}{|D|}Gini(D^v)$$\n",
    "- 数据集在属性a的基尼指数等于划分后各子集的归一化基尼系数之和\n",
    "- 在选择最优划分属性时，选择基尼指数最小的一个即可\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**基尼值和熵的比较**：\n",
    "\n",
    "- 基尼值实际是熵的近似：熵中的对数项$-log(p_k)$的泰勒展开的去除高阶项就是$1-p_k$。两者实际上很类似，都反映了不确定性。而基尼系数计算方便，所以很受欢迎。\n",
    "\n",
    "\n",
    "\n",
    "使用基尼指数选择最优划分属性依据的算法：\n",
    "\n",
    "- CART决策树\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 何时停止划分？\n",
    "决策树生成算法中出现三种情况时不用继续划分（会导致递归结束），当前节点会作为叶结点：\n",
    "1. 当前结点样本属于同一类别（标签相同）：将结点设置为该类别。\n",
    "2. 当前属性值为空（所有属性都以及被选择过划分属性）或者所有样本在所有属性上取值相同：将结点设置为**该结点中最多的类**的类别\n",
    "3. 当前结点包含的样本数为空（样本子集分完了）：将结点设为**父结点中最多的类**的类别"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树的剪枝（pruning）\n",
    "为了尽可能分类训练样本呢，划分将不断重复，可能导致分支过多。这样的决策树在训练集上的分类效果很好，而泛化能力很差。因此，可**去掉一些分支来降低过拟合，这就是剪枝**。\n",
    "\n",
    "剪枝分为预剪枝和后剪枝。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 预剪枝\n",
    "基本原理：**对每个结点划分前进行估计**，如果划分不能带来**决策树泛化能力**提升，则停止划分并将结点记为叶节点。\n",
    "\n",
    "具体步骤：\n",
    "- 对于每一个结点\n",
    "    - 计算划分前，该结点作为叶结点时决策树对于**验证集所有样本的分类准确率**。\n",
    "    - 计算划分后，令子结点为叶结点，计算此时决策树对于**验证集所有样本的分类准确率**。\n",
    "    - 若划分后验证集所有样本的分类准确率没有提升，则不该划分，否则进行划分。\n",
    "    \n",
    "预剪枝的优点：\n",
    "- 能减少结点划分，降低过拟合风险。\n",
    "- 减少决策树训练时间和测试时间（因为划分减少）。\n",
    "\n",
    "预剪枝的缺点：\n",
    "- 预剪枝基于贪心策略，有些情况下可能导致欠拟合（eg.本次划分可能降低泛化能力，但之后的划分能大大提高泛化能力）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 后剪枝\n",
    "基本原理：先根据训练集生成决策树，然后**自底向上对非叶节点进行评价**，若将该结点对应子树替换为叶结点能提高决策树泛化能力，则进行替换，否则不变。\n",
    "\n",
    "后剪枝的优点：\n",
    "- 后剪枝决策树相比于预剪枝决策树具有更多分支，因此欠拟合风险更小，泛化能力更强。\n",
    "\n",
    "后剪枝的缺点：\n",
    "- 后剪枝要在决策树完全生成后进行，且要自底向上对所有非叶结点进行考察，因此训练时间开销更大。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 连续值与缺失值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 连续值处理\n",
    "连续属性取值数目无限，因此不能像离散属性那样利用所有取值对结点进行划分，此时需要对连续属性进行离散化。\n",
    "\n",
    "**连续属性离散化有多种策略**：\n",
    "- 二分法（eg. C4.5）：将连续属性的所有取值从小到大排好，然后取任意相邻的两点的中点作为划分点。对于n个取值的属性值来说，其可能的划分点有n-1个。\n",
    "- 将连续属性的所有取值从小到大排好，然后取训练集中出现的不大于中位点的最大值作为划分点。\n",
    "\n",
    "**样本集D基于划分点t二分后的信息增益的数学描述**为：\n",
    "$$Gain(D,a)=max_{t \\in T_{a}} Gain(D,a,t)=max_{t \\in T_{a}}Ent(D)-\\sum _{\\lambda \\in \\{-,+\\}} \\frac{|D_t^{\\lambda}|}{|D|}Ent(D_t^{\\lambda})$$，其中$T_a$表示可能的划分点构成的集合。\n",
    "- 从上式可知，基于二分法的连续属性离散化是希望找到一个最优划分点，使得根据连续属性a进行划分的信息增益最大。\n",
    "\n",
    "**注意**：\n",
    "- 离散属性和连续属性不同：若某结点按照连续属性划分，那么这个属性还可以作为其子结点的划分属性。（eg：在某父节点使用了\"密度≤0.3\"，在子节点上不会禁止使用\"密度≤0.12\"）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 缺失值处理\n",
    "缺失值处理涉及两个问题：\n",
    "1. 如何在属性缺失情况下选择划分属性？\n",
    "2. 给定划分属性，若样本在该属性上缺失，如何对样本进行划分？\n",
    "\n",
    "### 选择划分属性\n",
    "假定为每个样本赋予一个权重，再定义三个量：\n",
    "\n",
    "![](https://camo.githubusercontent.com/50d6664a16251ec0c93d32ef2d0215eee6ea5e2f/68747470733a2f2f692e6c6f6c692e6e65742f323031382f31302f31372f356263373261303938663362652e706e67)\n",
    "\n",
    "其中，$\\tilde{D}$表示训练集$D$在属性a上没有缺失值的样本子集，$\\tilde{D}_k$表示$\\tilde{D}$中属于第k类的样本子集，$\\tilde{D}^v$表示$\\tilde{D}$中属性a上取值为$a^v$的样本子集。\n",
    "\n",
    "基于以上定义，样本在缺失属性a上的信息增益为：\n",
    "\n",
    "![](https://camo.githubusercontent.com/314ba7a17e21dbbf61e4bb25371bd2cec1d35889/68747470733a2f2f692e6c6f6c692e6e65742f323031382f31302f31372f356263373261303936636363332e706e67)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 对样本划分\n",
    "若该样本子集在属性a上的值缺失，则将该样本以不同的权重（即每个分支所含样本比例）划入到所有分支节点中。该样本在分支节点中的权重变为：\n",
    "$$\\omega_x=\\omega_x*\\tilde{r}_v\\$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 多变量决策树\n",
    "决策树形成的边界的一个特点就是**轴平行**（每个轴表示一个属性）。它的**优点**是学习结果解释性好，**缺点**是当分类边界复杂时，需要划分很多次才能得到较好近似，这时决策树会变得很复杂，时间开销也很大。\n",
    "\n",
    "**多变量决策树是能实现“斜划分”以及更复杂的划分的决策树**。\n",
    "\n",
    "多变量决策树的任务：找到一个合适的线性分类器。即每个非叶结点形如（可以理解成每个非叶结点的判别依据都是一个线性组合函数，如`-0.12*密度-0.3*含糖量≤0.02`）：\n",
    "$$\\sum_{i=1}^d\\omega_ia_i=t$$\n",
    "\n",
    "多变量决策树代表算法：\n",
    "- OC1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实例\n",
    "以下使用的sklearn实现的决策树实现，默认情况下，sklearn实现的CART决策树，采用基尼系数作为划分依据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实例一：简单的二分类\n",
    "训练集：生成两个点，每个点包含两个维度的特征（pro1、pro2），将样本分为两类（cls1、cls2）。\n",
    "训练决策树，并预测点（0，1）的类别：\n",
    "\n",
    "![](决策树.svg)\n",
    "- 观察到连续属性的离散化，即图中的`pro1≤0.5`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实例二：简单的回归\n",
    "sklearn中使用决策树进行回归分析由`DecisionTreeRegressor`类实现。\n",
    "\n",
    "首先，随机生成数据集（样本数：80，正弦型，每隔5个点随机引入噪声）。\n",
    "\n",
    "再设置树的深度分别为2、5、7，生成多个决策树分别预测。\n",
    "\n",
    "下面是预测结果展示：\n",
    "\n",
    "![](回归.png)\n",
    "- 从图中可以发现，当决策树深度增加时，拟合效果也逐渐，但是泛化能力有所降低(max_depth=5时比较好)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实例三：多输出回归\n",
    "有时会遇到多个值需要输出的多监督学习问题，与单一输出的回归不同，多输出回归需要改变叶节点的输出值为多个。\n",
    "\n",
    "数据：输入是单一变量x（100,1），输出y（100,2）是x的正弦和余弦值，输出值在二维平面上呈圆形。\n",
    "\n",
    "训练：分别设置树深度为2、5、8，得到三个决策树，进行预测。\n",
    "\n",
    "可视化：\n",
    "\n",
    "![](多输出回归.png)\n",
    "- 随着树深度增大，拟合效果越来越好（深度为8时输出值最接近于圆）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 小结\n",
    "ID3:\n",
    "- 优点：算法简单，通俗易懂\n",
    "- 缺点：\n",
    "    1. 无法处理缺失值\n",
    "    2. 只能处理离散值，无法处理连续值\n",
    "    3. 用信息增益作为划分规则，存在偏向于选择取值较多的特征。因为特征取值越多，说明划分的越细，不确定性越低，信息增益则越高\n",
    "    4. 容易出现过拟合\n",
    "\n",
    "C4.5:\n",
    "- 优点：\n",
    "    1. 能够处理缺省值\n",
    "    2. 能对连续值做离散处理\n",
    "    3. 使用信息增益比，能够避免偏向于选择取值较多的特征。因为信息增益比=信息增益/属性熵，属性熵是根据属性的取值来计算的，可以避免决策树往多个类的方向划分\n",
    "    4. 在构造树的过程中，会剪枝，减少过拟合\n",
    "- 缺点：构造决策树，需要对数据进行多次扫描和排序，效率低"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
